package org.tlang.parser;

import org.tlang.exception.ParseException;
import org.tlang.lexer.Lexer;
import org.tlang.lexer.token.Token;
import org.tlang.ast.AST;
import org.tlang.ast.ASTLeaf;
import org.tlang.ast.list.expr.BinaryExpr;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class ExprParser extends Parser {
    private static final Map<String, Priority> OPERATORS = new HashMap<String, Priority>() {{
        Priority priority;
        int value = 0;

        priority = new Priority(++value, false);
        put("=", priority);

        priority = new Priority(++value, true);
        put("||", priority);

        priority = new Priority(++value, true);
        put("&&", priority);

        priority = new Priority(++value, true);
        put("==", priority);
        put("!=", priority);

        priority = new Priority(++value, true);
        put(">", priority);
        put("<", priority);
        put("<=", priority);
        put(">=", priority);

        priority = new Priority(++value, true);
        put("+", priority);
        put("-", priority);

        priority = new Priority(++value, true);
        put("*", priority);
        put("/", priority);
        put("%", priority);

        priority = new Priority(++value, true);
        put(".", priority);
    }};

    public ExprParser(Lexer lexer) {
        super(lexer);
    }

    /**
     * 根据下一个运算符的优先级判断当前运算符是个子表达式，还是运算数字
     * example: a + b * c, 返回true，代表右侧的b*c是一个子表达式，需要独立计算
     * example: a + b + c, 返回false，代表右侧b是个运算数
     * example: m.a = b * c,
     *
     * @param priority     当前运算符的优先级
     * @param nextPriority 下一个运算符的优先级及结合顺序（左/右结合）
     * @return boolean
     */
    private boolean rightIsExpr(int priority, Priority nextPriority) {
        if (nextPriority.leftAssoc) { // 后一个运算符左结合
            return priority < nextPriority.value;
        } else { // 后一个运算符右结合
            return priority <= nextPriority.value;
        }
    }

    /**
     * 获取下一个操作符的优先级
     */
    private Priority nextOpPri() {
        Token token = lexer.peek(0);
        if (token.isIdentifier()) {
            return OPERATORS.get(token.getText());
        } else {
            return null;
        }
    }

    /**
     * 右移计算表达式
     *
     * @param left     左侧表达式
     * @param priority 右侧下一个操作符的优先级
     */
    private AST shiftRight(AST left, int priority) throws ParseException {
        ASTLeaf op = new ASTLeaf(lexer.poll());
        AST right = factor();
        Priority nextOpPri;
        while ((nextOpPri = nextOpPri()) != null && rightIsExpr(priority, nextOpPri)) {
            right = shiftRight(right, nextOpPri.value);
        }
        return new BinaryExpr(Arrays.asList(left, op, right));
    }

    /**
     * expr: factor { OP factor }
     * 支持的运算符范围由 OPERATORS 定义
     */
    @Override
    protected AST expr() throws ParseException {
        AST right = factor();
        Priority nextOpPri;
        while ((nextOpPri = nextOpPri()) != null) {
            right = shiftRight(right, nextOpPri.value);
        }
        return right;
    }

    @Override
    public AST parse(Lexer lexer) throws ParseException {
        this.lexer = lexer;
        return expr();
    }

    /**
     * 运算符优先级和结合顺序
     * value: 数字越大优先级越高
     * leftAssoc: true: 左结合（从左向右计算）, false：右结合（从右向左计算）
     */
    private static final class Priority {
        private final int value;
        private final boolean leftAssoc; // left associative

        Priority(int value, boolean leftAssoc) {
            this.value = value;
            this.leftAssoc = leftAssoc;
        }
    }
}
